﻿//给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
//树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
//
//输入：root = [1, null, 3, 2, 4, null, 5, 6]
//输出： [[1], [3, 2, 4], [5, 6]]
//
//输入：root = [1, null, 2, 3, 4, 5, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14]
//输出： [[1], [2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13], [14]]
//
//提示：
//
//树的高度不会超过 1000
//树的节点总数在[0, 10^4] 之间

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret; // 记录最终结果

        queue<Node*> q; // 层序遍历需要的队列

        if (root == nullptr)
            return ret;
        q.push(root);
        while (q.size()) {
            int sz = q.size(); // 先求出本层元素的个数

            vector<int> tmp; // 统计本层的节点

            for (int i = 0; i < sz; i++) {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for (Node* child : t->children) // 让下⼀层结点⼊队

                {
                    if (child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};